MacHack 2000/MacHack 2000.toast/pc/The Hacks/Softshoe/Lisa's Mac Parts/Heap/Heap.cp

Text File | 2000-06-23 | 5KB | 268 lines

// Heap.cp
#define Heap_cp

#ifndef Heap_h
#include "Heap.h"
#endif
#ifndef HeapLink_h
#include "HeapLink.h"
#endif
#ifndef Swap_h
#include "Swap.h"
#endif

template< class Element >
Heap< Element >::Heap( Comparator compare )
  : nodeCount( 0 ),
     top( 0 ),
     below( compare )
  {
    Assert( compare != 0 );
  }

template< class Element >
Heap< Element >::~Heap()
  {
    Assert( nodeCount == 0 );
    Assert( top == 0 );
  }

template< class Element >
HeapLink<Element>& Heap< Element >::Pop()
  {
    HeapLink<Element>& result = Top();
    Remove( result );
    return result;
  }

template< class Element >
void Heap< Element >::Add( LinkType& toAdd )
  {
    Assert( toAdd.heap == 0 );
    toAdd.heap = this;

    Assert( toAdd.children[0] == 0 );
    Assert( toAdd.children[1] == 0 );

    toAdd.path = ++nodeCount;

    LinkType **subHeap = ⊤
    LinkType *carrying = &toAdd;
    SinkNode( subHeap, carrying );

    Assert( *subHeap == 0 );
    Assert( carrying->path == nodeCount );
    Assert( carrying->children[0] == 0 );
    Assert( carrying->children[1] == 0 );

    *subHeap = carrying;
  }

template< class Element >
void Heap< Element >::Remove( LinkType& toRemove )
  {
    Assert( toRemove.heap == this );
    Assert( nodeCount > 0 );

    LinkType *spare( &RemoveLast() );

    if ( spare != &toRemove )
      {
        LinkType **subHeap = ⊤
        spare->path = toRemove.path;
        SinkNode( subHeap, spare );

        Assert( *subHeap == &toRemove );
        Assert( spare->path == toRemove.path );

        *subHeap = spare;
        toRemove.SwapWith( *spare );
        Percolate( subHeap );
      }

    toRemove.heap = 0;
    Assert( toRemove.children[0] == 0 );
    Assert( toRemove.children[1] == 0 );
  }


template< class Element >
HeapLink<Element>** Heap< Element >::SubHeap( uint32 path )
  {
    Assert( path <= nodeCount );
    Assert( path >= 1 );

    LinkType **subHeap = ⊤
    uint32 remainingPath = path;

    while ( remainingPath > 1 )
      {
        Assert( *subHeap != 0 );
        subHeap = &(*subHeap)->children[ remainingPath % 2 ];
        remainingPath /= 2;
      }

    Assert( *subHeap != 0 );
    Assert( (*subHeap)->path == path );
    return subHeap;
  }

template< class Element >
HeapLink<Element>& Heap< Element >::RemoveLast()
  {
    Assert( nodeCount > 0 );
    LinkType **subHeap = SubHeap( nodeCount );
    LinkType& removed = **subHeap;
    *subHeap = 0;

    Assert( removed.children[0] == 0 );
    Assert( removed.children[1] == 0 );
    Assert( removed.heap == this );
    Assert( removed.path == nodeCount );
    removed.path = 0;
    nodeCount--;

    return removed;
  }

template< class Element >
void Heap< Element >::SinkNode( LinkType**& subHeap,
                                          LinkType*& carrying )
  {
    Assert( subHeap != 0 );
    Assert( carrying != 0 );

    uint32 path = carrying->path;

    while( path > 1 )
      {
        Assert( *subHeap != 0 );

        if ( **subHeap > *carrying )
          {
            (*subHeap)->SwapWith( *carrying );
            Swap( *subHeap, carrying );
          }

        Assert( path > 1 );
        subHeap = &(*subHeap)->children[ path % 2 ];
        path /= 2;
      }

    Assert( path == 1 );
  }

template< class Element >
void Heap< Element >::Percolate( LinkType** subHeap )
  {
    LinkType& dropping( **subHeap );

    while( true )
      {
        Assert( *subHeap == &dropping );

        LinkType *left = dropping.children[0];
        LinkType *right = dropping.children[1];

        if ( left == 0 )
          {
            Assert( right == 0 );
            break;
          }

        if ( dropping > *left && ( right == 0 || *left <= *right ) )
          {
            dropping.SwapWith( *left );
            Swap( *subHeap, left->children[0] );

            Assert( left->children[0] == &dropping );
            Assert( *subHeap == left );

            subHeap = &left->children[0];
            continue;
          }

        if ( right == 0 )
            break;

        if ( dropping > *right )
          {
            dropping.SwapWith( *right );
            Swap( *subHeap, right->children[1] );

            Assert( right->children[1] == &dropping );
            Assert( *subHeap == right );

            subHeap = &right->children[1];
            continue;
          }

        break;
      }
  }

template< class Element >
void Heap< Element >::Validate( LinkType& node, uint32 level ) const
  {
    Assert( node.path > 0 );
    Assert( node.path <= nodeCount );
    Assert( node.heap == this );
    Assert( !node.Null() );

    uint32 topBit = 1L << level;

    Assert( (node.path & topBit) != 0 );
    Assert( node.path <= ( 2*topBit - 1) );

    if ( level == 31 )
      {
        Assert( node.children[0] == 0 );
        Assert( node.children[1] == 0 );
        return;
      }

    uint32 rightChild = node.path | (topBit << 1);
    uint32 leftChild = rightChild & ~topBit;

    if ( node.children[0] == 0 )
      {
        Assert( leftChild > nodeCount );
      }
     else
      {
        Assert( leftChild <= nodeCount );
        Assert( node.children[0]->path == leftChild );
        Assert( node <= *node.children[0] );
        Validate( *node.children[0], level+1 );
      }

    if ( node.children[1] == 0 )
      {
        Assert( rightChild > nodeCount );
      }
     else
      {
        Assert( rightChild <= nodeCount );
        Assert( node.children[1]->path == rightChild );
        Assert( node <= *node.children[1] );
        Validate( *node.children[1], level+1 );
      }
  }

template< class Element >
void Heap< Element >::Validate() const
  {
    Assert( below != 0 );

    if ( nodeCount == 0 )
      {
        Assert( top == 0 );
      }
     else
      {
        Assert( top != 0 );
        Assert( top->path == 1 );
        Validate( *top, 0 );
      }
  }